package com.datastructure.test.calarray;

import java.util.ArrayList;

public class CalArray {

    public static void main(String[] args) {

    }

    public long calArray (ArrayList<Integer> nums) {
        // write code here
        if(nums == null || nums.size() <= 1){
            return 0;
        }

        int[] arr = nums.stream().mapToInt(x -> x).toArray();

        return process(arr,0,arr.length - 1);
    }

    public static long process(int[] arr, int l, int r) {
        // 如果只有一个数，不能比较大小，那小和的和就是0
        if (l == r) {
            return 0;
        }

        int mid = l + ((r - l) >> 1);
        // 左边 0 ~ mid 上产生的小和
        long left = process(arr, l, mid);
        // 右边 mid+1 ~ length-1 上产生的小和
        long right = process(arr, mid + 1, r);
        // 0 到 length -1 上的小和
        long merge = merge(arr, l, mid, r);

        return left + right + merge;
    }

    private static long merge(int[] arr, int l, int mid, int r) {
        int i = 0;
        int p1 = l;
        int p2 = mid + 1;
        int[] help = new int[r - l + 1];

        long sum = 0;
        while (p1 <= mid && p2 <= r) {

            sum  += arr[p1] <= arr[p2] ? (long) (r - p2 + 1) * arr[p1] : 0;
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }

        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }

        while (p2 <= r) {
            help[i++] = arr[p2++];
        }

        for (i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }

        return sum;
    }
}
